package E_2024;

import java.util.Arrays;

/*
    双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金。
    现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。
输入描述:
    输入第一行为一维整型数组M，数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000。
    输入第二行为购买资金的额度R，R小于100000。
输出描述:
    输出为满足上述条件的最大花费额度。
    注意：
    如果不存在满足上述条件的商品，请返回-1。
示例1  输入输出示例仅供调试，后台判题数据一般不包含示例
    输入
    23,26,36,27
    78
    输出
    76
    说明
    金额23、26和27相加得到76，而且最接近且小于输入金额78。
 */
public class E_100_39 {
    public static void main(String[] args) {
        System.out.println(ans1(new int[]{23,26,36,27},78));
    }
    public static int ans1(int[] arr, int money){
        int max = -1;
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            int x = arr[i];
            int left = i + 1;
            int right = arr.length - 1;
            while(left < right){
                if (x + arr[left] + arr[right] > money) right--;
                else if (x + arr[left] + arr[right] < money) {
                    max = Math.max(max,x + arr[left] + arr[right]);
                    left++;
                }
                else return x + arr[left] + arr[right];
            }
        }
        return max;
    }
    // 暴力枚举
    public static int ans(int[] arr, int money){
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > money) continue;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] + arr[j] > money) continue;
                for (int k = j+1; k < arr.length; k++) {
                    if (arr[i] + arr[j] + arr[k] <= money) max = Math.max(max,arr[i] + arr[j] + arr[k]);
                }
            }
        }
        return max;
    }
}
